package summary;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/16 9:04
 * https://leetcode-cn.com/problems/repeated-dna-sequences/
 */
public class Title187 {

    final static int L = 10;

    public static List<String> findRepeatedDnaSequences(String s) {
        List<String> result = new ArrayList<>();
        Map<String, Integer> hash = new HashMap<>();
        for (int i = 0; i <= s.length() - L; i++) {
            String substring = s.substring(i, i + L);
            hash.put(substring, hash.getOrDefault(substring, 0) + 1);
            Integer integer = hash.get(substring);
            if (integer == 2) {
                result.add(substring);
            }
        }
        return result;
    }

    final static  Map<Character,Integer> dna = new HashMap<Character,Integer>(){
        {
            //每位字符占两位
            put('A', 0);
            put('C', 1);
            put('G', 2);
            put('T', 3);
        }
    };

    public static List<String> findRepeatedDnaSequences1(String s) {
        List<String> result = new ArrayList<>();
        if (s.length() <= L) {
            return result;
        }
        //字符串改用int类型存储
        Map<Integer, Integer> hash = new HashMap<>();
        int x = 0;
        for (int i = 0; i < L - 1; i++) {
            x = (x << 2) | dna.get(s.charAt(i));
        }
        for (int i = L - 1; i < s.length(); i++) {
            //维持大小为L的窗口（消除最左边的字符 2位）
            x = ((x << 2) | dna.get(s.charAt(i))) & ((1 << (L * 2)) - 1);
            hash.put(x, hash.getOrDefault(x, 0) + 1);
            if (hash.get(x) == 2) {
                result.add(s.substring(i - L + 1, i + 1));
            }
        }
        return result;
    }

    public static List<String> findRepeatedDnaSequences2(String s) {
        if (s.length() <= 10) {
            return new ArrayList<>();
        }
        Set<String> set = new HashSet<>();
        Set<String> set2 = new HashSet<>();
        for (int i = 0; i <= s.length() - L; i++) {
            String temp = s.substring(i, i + L);
            if (!set.add(temp)) {
                set2.add(temp);
            }
        }
        return new ArrayList<>(set2);
    }

    public static void main(String[] args) {
        String s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT";
        findRepeatedDnaSequences2(s);
    }
}
